#include <vector>

using namespace std;

class Solution {
public:
    // 1137. 第 N 个泰波那契数
    // https://leetcode.cn/problems/n-th-tribonacci-number/
    int tribonacci(int n) {
        if (n<=2)
        {
            if (n==0) return 0;
            else return 1;
        }
        
        int a = 0, b = 1, c = 1, d = 0;
        for (int i = 3; i<=n; ++i)
        {
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }

    // 面试题 08.01. 三步问题
    // https://leetcode.cn/problems/three-steps-problem-lcci/
    // int waysToStep(int n) {
    //     if (n <= 2) return n;
    //     else if (n == 3) return 4;
        
    //     const static int MOD = 1e9 + 7;
    //     vector<int> dp(n+1);
    //     dp[1] = 1, dp[2] = 2, dp[3] = 4;
    //     for (int i = 4; i<=n; ++i)
    //     {
    //         dp[i] = (((dp[i-1] + dp[i-2]) % MOD) + dp[i-3]) % MOD;
    //     }
    //     return dp[n];
    // }
    // 优化
    int waysToStep(int n) {
        if (n <= 2) return n;
        else if (n == 3) return 4;
        
        const static int MOD = 1e9 + 7;
        
        int a = 1, b = 2, c = 4, d = 0;
        for (int i = 4; i<=n; ++i)
        {
            d = (((a + b) % MOD) + c) % MOD;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }

    // 746. 使用最小花费爬楼梯
    // https://leetcode.cn/problems/min-cost-climbing-stairs/
    // 法一：i为终点
    int minCostClimbingStairs(vector<int>& cost) {
        int size = cost.size();
        vector<int> dp(size+1);
        dp[0] = dp[1] = 0;
        for (int i = 2; i<=size; ++i)
        {
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        return dp[size];
    }
    // 法二：i为起点
    int minCostClimbingStairs(vector<int>& cost) {
        int size = cost.size();
        vector<int> dp(size);
        dp[size-1] = cost[size-1];
        dp[size-2] = cost[size-2];
        for (int i = size-3; i>=0; --i)
        {
            dp[i] = min(dp[i+1] + cost[i], dp[i+2] + cost[i]);
        }
        return min(dp[0], dp[1]);
    }
};